package org.kevinth.sudoku;

import java.io.BufferedReader;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.EmptyStackException;
import java.util.List;
import java.util.Set;
import java.util.Stack;
import java.util.TreeSet;

/**
 * @author <a href="mailto:tulkas.web@gmail.com">Tulkas</a>
 *
 */
public class SudokuResolver {
	public static final int MAX_ITERATE = 1000;

	protected int len = 0;
	protected int groupSize = 0;
	protected Cell[][] cells = null;
	protected int unResolved = 0;
	protected Stack<ChangeLog> changeLogs = new Stack<ChangeLog>();
	protected boolean changed = false;
	protected List<int[][]> outputs = new ArrayList<int[][]>();

	@Override
	public String toString() {
		String str = "";
		for (int i = 0; i < len; i++) {
			for (int j = 0; j < len; j++) {
				str += String.valueOf(cells[i][j].value);
			}
			str += "\n";
		}
		return str;
	}

	protected void processCells() {
		for (int i = 0; i < len; i++) {
			for (int j = 0; j < len; j++) {
				if (cells[i][j].value == 0) {
					unResolved++;
					processFixedCandidates(i, j);
				}
			}
		}

		while (true) {
			try {
				processIterate();
			} catch (TestFailException e) {
				if (popAndRestore()) {
					break;
				}
			}

			if (unResolved > 0)
				try {
					processTest();
				} catch (TestFailException e) {
					if (popAndRestore()) {
						break;
					}
				}
			else {
				output();
				if (popAndRestore()) {
					break;
				}
			}
		}
	}

	protected boolean popAndRestore() {
		boolean ret = false;
		boolean loop = false;
		do {
			ChangeLog cl;
			try {
				cl = changeLogs.pop();
			} catch (EmptyStackException e1) {
				return true;
			}

			try {
				cl.restoreAndExclude();
			} catch (TestFailException e) {
				loop = true;
				continue;
			}
			loop = false;
		} while (loop == true);

		return ret;
	}

	protected void output() {
		int[][] out = new int[len][];
		for (int i = 0; i < len; i++) {
			out[i] = new int[len];
			for (int j = 0; j < len; j++) {
				out[i][j] = cells[i][j].value;
			}
		}
		System.out.println();
		System.out.println("output:");
		for (int u = 0; u < len; u++) {
			for (int o = 0; o < len; o++) {
				System.out.print(out[u][o]);
			}
			System.out.println();
		}
		outputs.add(out);
	}

	protected void processTest() {
		int iw = 0;
		int jw = 0;
		int minC = 10;
		label: for (int i = 0; i < len; i++) {
			for (int j = 0; j < len; j++) {
				if (cells[i][j].value == 0) {
					int size = cells[i][j].candidates.size();
					if (minC > size) {
						minC = size;
						iw = i;
						jw = j;
						if (minC <= 2)
							break label;
					}
				}
			}
		}

		if (minC == 10 || minC < 2)
			throw new RuntimeException("Error");

		ChangeLog cl = new ChangeLog(iw, jw);
		changeLogs.push(cl);
		gotAnValue(iw, jw, cl.value);
	}

	protected void processIterate() {
		do {
			if (unResolved == 0)
				break;
			changed = false;
			for (int i = 0; i < len; i++) {
				for (int j = 0; j < len; j++) {
					checkCandidate(i, j);
				}
			}
		} while (changed == true);
	}

	protected void processFixedCandidates(int i, int j) {
		Set<Integer> canNot = new TreeSet<Integer>();
		for (int k = 0; k < len; k++) {
			if (cells[i][k].value != 0) {
				canNot.add(cells[i][k].value);
			}
		}

		for (int k = 0; k < len; k++) {
			if (cells[k][j].value != 0) {
				canNot.add(cells[k][j].value);
			}
		}

		if (groupSize != 0) {
			int is = i / groupSize * groupSize;
			int js = j / groupSize * groupSize;
			for (int ii = is; ii < is + groupSize; ii++) {
				for (int jj = js; jj < js + groupSize; jj++) {
					if (cells[ii][jj].value != 0) {
						canNot.add(cells[ii][jj].value);
					}
				}
			}
		}

		for (int q = 1; q <= len; q++) {
			if (!canNot.contains(q)) {
				cells[i][j].candidates.add(q);
			}
		}
	}

	protected void checkCandidate(int i, int j) {
		if (cells[i][j].value != 0)
			return;
		if (cells[i][j].candidates.size() == 1) {
			gotAnValue(i, j, cells[i][j].candidates.iterator().next());
		} else if (cells[i][j].candidates.size() == 0) {
			throw new TestFailException();
		}
	}

	protected void gotAnValue(int i, int j, int value) {
		cells[i][j].value = value;
		unResolved--;
		changed = true;

		for (int k = 0; k < len; k++) {
			if (cells[i][k].value == 0) {
				cells[i][k].candidates.remove(value);
			}
		}

		for (int k = 0; k < len; k++) {
			if (cells[k][j].value == 0) {
				cells[k][j].candidates.remove(value);
			}
		}

		if (groupSize != 0) {
			int is = i / groupSize * groupSize;
			int js = j / groupSize * groupSize;
			for (int ii = is; ii < is + groupSize; ii++) {
				for (int jj = js; jj < js + groupSize; jj++) {
					if (cells[ii][jj].value == 0) {
						cells[ii][jj].candidates.remove(value);
					}
				}
			}
		}
	}

	public List<int[][]> resolve(int[][] input) {
		len = 0;
		groupSize = 0;
		cells = null;
		if (input.length != input[0].length) {
			throw new IllegalArgumentException();
		}

		len = input.length;
		float lf = (float) len;
		float gt = (float) Math.sqrt(lf);
		if (gt - Math.floor(gt) < 0.0001f) {
			groupSize = Math.round(gt);
		}

		cells = new Cell[len][];
		for (int i = 0; i < len; i++) {
			cells[i] = new Cell[len];
			for (int j = 0; j < len; j++) {
				cells[i][j] = new Cell();
				cells[i][j].value = input[i][j];
			}
		}

		processCells();
		return outputs;
	}

	static class TestFailException extends RuntimeException {
		private static final long serialVersionUID = -2301056269934258836L;

		public TestFailException() {
			super();
		}
	}

	static class Cell implements Cloneable {
		int value = 0;
		Set<Integer> candidates = new TreeSet<Integer>();

		@Override
		public String toString() {
			if (value != 0)
				return String.valueOf(value);
			else
				return candidates.toString();
		}

		@Override
		protected Object clone() throws CloneNotSupportedException {
			Cell ret = new Cell();
			ret.value = value;
			ret.candidates.addAll(candidates);
			return ret;
		}
	}

	class ChangeLog {
		int i = 0;
		int j = 0;
		int value = 0;
		int oriUnResolved = 0;

		Cell[][] originalCells = null;

		public ChangeLog(int i, int j) {
			this.i = i;
			this.j = j;
			this.oriUnResolved = unResolved;
			originalCells = new Cell[len][];
			for (int u = 0; u < len; u++) {
				originalCells[u] = new Cell[len];
				for (int o = 0; o < len; o++) {
					try {
						originalCells[u][o] = (Cell) cells[u][o].clone();
					} catch (CloneNotSupportedException e) {
						throw new RuntimeException(e);
					}
				}
			}
			this.value = cells[i][j].candidates.iterator().next();
		}

		public void restoreAndExclude() {
			cells = originalCells;
			unResolved = oriUnResolved;

			cells[i][j].candidates.remove(value);
			processIterate();
		}
	}

	public static void main(String[] args) {
		try {
			BufferedReader reader = new BufferedReader(new FileReader(
					"f:/tmp/sudoku.txt"));
			List<Integer> il = new ArrayList<Integer>();
			int noAnswerCount = 0;
			long mill1 = System.currentTimeMillis();
			int count = 10;
			for (int i = 0; i < count; i++) {
				SudokuResolver resolver = new SudokuResolver();
				il.clear();
				String line = reader.readLine();
				if (line != null) {
					line = line.trim();
					for (int j = 0; j < line.length(); j++) {
						char c = line.charAt(j);
						il.add(c - '0');
					}

					double ld = Math.sqrt(il.size());
					if (ld - Math.floor(ld) > 0.00001) {
						System.out
								.println("number count error! [" + line + "]");
					} else {

						int len = (int) Math.round(ld);
						int[][] input = new int[len][];
						for (int u = 0; u < len; u++) {
							input[u] = new int[len];
							for (int o = 0; o < len; o++) {
								input[u][o] = il.get(u * len + o);
							}
						}
						System.out.println();
						System.out.println("input:");
						for (int u = 0; u < len; u++) {
							for (int o = 0; o < len; o++) {
								System.out.print(input[u][o]);
							}
							System.out.println();
						}
						try {
							List<int[][]> outputs = resolver.resolve(input);

							if (outputs.size() == 0) {
								System.out.println("No Answer");
								noAnswerCount++;
							} else {
								//								System.out.println("Output Count:"
								//										+ outputs.size());
							}
						} catch (RuntimeException e) {
							e.printStackTrace();
						}

					}
				}
			}
			long mill2 = System.currentTimeMillis();
			System.out.println("Velocity=" + ((double) mill2 - (double) mill1)
					/ count);

			System.out.println("No Answer Count: " + noAnswerCount);
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
}
